#include<stdio.h>
#include<stdlib.h>
#include<math.h>


#define STACKMAXSIZE 50
typedef int StackElemType;
typedef struct
{
	StackElemType elem[STACKMAXSIZE];
	int top;
} SeqStack;

//初始化 
void InitSeqStack(SeqStack* S)
{
	S->top = -1;
}
//入栈 
int PushStack(SeqStack* S, StackElemType e)
{
	if (S->top >= STACKMAXSIZE - 1)
	{
		printf("栈满！\n");
		return 0;
	}
	S->top++;
	S->elem[S->top] = e;
	return 1;
}
//出栈 
int PopStack(SeqStack* S, StackElemType* e)
{
	if (S->top < 0)
	{
		printf("栈空！\n");
		return 0;
	}
	*e = S->elem[S->top];
	S->top--;
	return 1;
}
//获取栈顶元素 
int GetTop(SeqStack *S, StackElemType* e)
{
	if (S->top <0)
	{
		printf("栈空！\n");
		return 0;
	}
	*e = S->elem[S->top];
	return 1;
}
//运算符优先级计算 
int Prior(char ch)
{
	if (ch == '+' || ch == '-')return 1;
	else if (ch == '*' || ch == '/' || ch == '^')return 2;
	else if (ch == '(')return 0;
	else return -1;
}

//判断字符ch是否为操作数 
int IsOpNum(char ch)
{
	if (ch >= '0' && ch <= '9')return 1;
	else return 0;
}

//读取多位数
int GetNumber(char** str)
{
	int num = 0;
	while (IsOpNum(**str))
	{
		num = num * 10 + (**str - '0');
		(*str)++;
	}
	return num;
}
//幂的运算
int Power(int v1, int v2)
{
	return (int)pow(v1, v2);
}

//表达式的求值 
int ExpEvaluation(char *str)
{
	int i;
	int n;
	char v1, v2, op, e;
	SeqStack S1, S2;
	
	InitSeqStack(&S1);
	InitSeqStack(&S2);
	
	PushStack(&S1, '#');
	i = 0;
	while (str[i])
	{
		if (IsOpNum(str[i]))
		{
			n = GetNumber(&str);
			PushStack(&S2, n);
		}
		else
		{
			GetTop(&S1, &e);
			if (str[i] == '#' && e == '#')break;
			if (str[i] == '(')
			{
				PushStack(&S1, str[i]);
				i++;
			}
			else if (str[i] == ')')
			{
				while (e != '(')
				{
					PopStack(&S1, &op);
					PopStack(&S2, &v2);
					PopStack(&S2, &v1);
					switch (op)
					{
						case '+': PushStack(&S2, v1 + v2);break;
						case '-': PushStack(&S2, v1 - v2);break;
						case '*': PushStack(&S2, v1 * v2);break;
						case '/': PushStack(&S2, v1 / v2);break;
						case '^': PushStack(&S2, Power(v1, v2));break;
					}
					GetTop(&S1, &e);
				}
				PopStack(&S1, &op);
				i++;
			}
			else if (Prior(str[i]) > Prior(e))
			{
				PushStack(&S1, str[i]);
				i++;
			}
			else
			{
				PopStack(&S1, &op);
				PopStack(&S2, &v2);
				PopStack(&S2, &v1);
				switch (op)
				{
					case '+': PushStack(&S2, v1 + v2);break;
					case '-': PushStack(&S2, v1 - v2);break;
					case '*': PushStack(&S2, v1 * v2);break;
					case '/': PushStack(&S2, v1 / v2);break;
					case '^': PushStack(&S2, Power(v1, v2));break;
				} //switch 
			}//else
		}//else
	}//while
	PopStack(&S2, &n);
	return n;
}

int main()
{
	int v;
	char str[80];
	printf("输入一个表达式，以#为结束！\n");
	gets(str);
	v = ExpEvaluation(str);
	printf("该表达式的运算结果为：%d\n", v);
	return 0;
}
